package com.peng.leetcode.tree;

/**
 * FlipEquiv
 * <p>
 * 951. 翻转等价二叉树
 *
 * @author: lupeng6
 * @create: 2021/1/28 10:54
 */
public class FlipEquiv {

    public static void main(String[] args) {
        TreeNode treeNode = TreeMain.array2tree(new Integer[]{1, 2, 3, 4, 5, 6, null, null, null, 7, 8});
        TreeNode treeNode1 = TreeMain.array2tree(new Integer[]{1, 3, 2, null, 6, 4, 5, null, null, null, null, 8, 7});
        System.out.println(new FlipEquiv().flipEquiv(treeNode, treeNode1));
    }


    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 != null && root2 == null) {
            return false;
        }
        if (root1 == null && root2 != null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        boolean flag1 = flipEquiv(root1.left, root2.left);
        boolean flag2 = flipEquiv(root1.left, root2.right);

        boolean flag3 = flipEquiv(root1.right, root2.left);
        boolean flag4 = flipEquiv(root1.right, root2.right);

        if ((flag1 || flag2) && (flag3 || flag4)) {
            return true;
        } else {
            return false;
        }
    }
}
